package algorithm.linkedlist;

/**
 * 反转单链表 LC206
 *
 * @author 杨 强
 * @package algorithm.linkedlist
 * @createTime 2023-03-09 21:40
 */
public class Reversal03 {
    public static void main(String[] args) {
        // 定义一个链表[1,2,3,4,5]
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        // 反转链表并返回头部节点
        ListNode n1 = reversal03(o1);
        System.out.println(n1);
    }

    /**
     * 翻转单链表-递归
     * @param o1
     * @return
     */
    private static ListNode reversal03(ListNode o1) {
        if (o1 == null || o1.next == null){
            // 最后的节点
            return o1;
        }
        // 当前节点的下一个节点
        ListNode listNode = reversal03(o1.next);

        // 当前节点的下一个节点的下一个节点指向当前节点
        o1.next.next = o1;

        // 当前节点的下一个节点指向为空
        o1.next = null;

        // 返回当前节点的下一个节点
        return listNode;
    }

}
